package likou;

import java.util.Arrays;

/**
 * @Info:
 * @Author: 唐小尊
 * @Date: 2020/4/20  17:28
 */
public class _200 {
    public static int numIslands(char[][] grid) {
        int i, j;
        int hang = grid.length;
        int lie = grid[0].length;
        int yibianli[][] = new int[hang][lie];
        int num = 0;
        for (i = 0; i < hang; i++) {
            for (j = 0; j < lie; j++) {
                if (yibianli[i][j] == 1) {
                    continue;
                }
                if (grid[i][j] == '1') {
                    zhao(grid, yibianli, i, j);
                    num++;
                } else {
                    yibianli[i][j] = 1;
                }
            }
        }
        return num;
    }

    public static void zhao(char[][] grid, int[][] yibianli, int i, int j) {
        if (yibianli[i][j] == 1) {
            return;
        } else {
            yibianli[i][j] = 1;
            if (j + 1 < grid[0].length) {
                if (grid[i][j + 1] == '1' && yibianli[i][j + 1] != 1) {
//                    System.out.println("右遍历" + i + "   " + (j + 1));
                    zhao(grid, yibianli, i, j + 1);
                    yibianli[i][j + 1] = 1;
                } else {
//                    System.out.println("右遍历" + i + "   " + (j + 1));
                    yibianli[i][j + 1] = 1;
                }
            }
            if (j > 0) {
                if (grid[i][j - 1] == '1' && yibianli[i][j - 1] != 1) {
//                    System.out.println("左遍历" + i + "   " + (j - 1));
                    zhao(grid, yibianli, i, j - 1);
                    yibianli[i][j - 1] = 1;
                } else {
//                    System.out.println("左遍历" + i + "   " + (j - 1));
                    yibianli[i][j - 1] = 1;
                }
            }
            if (i + 1 < grid.length) {
                if (grid[i + 1][j] == '1' && yibianli[i + 1][j] != 1) {
//                    System.out.println("下遍历" + (i + 1) + "   " + j);
                    zhao(grid, yibianli, i + 1, j);
                    yibianli[i + 1][j] = 1;
                } else {
//                    System.out.println("下遍历" + (i + 1) + "   " + j);
                    yibianli[i + 1][j] = 1;
                }
            }
            if (i > 0) {
                if (grid[i - 1][j] == '1' && yibianli[i - 1][j] != 1) {
//                    System.out.println("上遍历" + (i - 1) + "   " + j);
                    zhao(grid, yibianli, i - 1, j);
                    yibianli[i - 1][j] = 1;
                } else {
//                    System.out.println("上遍历" + (i - 1) + "   " + j);
                    yibianli[i - 1][j] = 1;
                }
            }
        }

    }

    public static void main(String[] args) {
        char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        char[][] grid2 = {{'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'}};

        char[][] grid3 = {{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}};
        for (int i = 0; i < grid3.length; i++) {
            for (int j = 0; j < grid3[0].length; j++) {
                System.out.print(grid3[i][j]);
            }
            System.out.println();
        }
        System.out.println(numIslands(grid));
        System.out.println("***************************");
        System.out.println(numIslands(grid2));
        System.out.println("***************************");
        System.out.println(numIslands(grid3));
        System.out.println("***************************");
    }
}